package com.lijing.BackTracing1;

import java.util.*;

/**
 * @Description 给定⼀个仅包含数字 2-9 的字符串，返回所有它能表示的字⺟组合。
 * 给出数字到字⺟的映射如下（与电话按键相同）。注意 1 不对应任何字⺟。
 * @title: Combination3
 * @Author LiJing
 * @Date: 2021/4/53:54 下午
 * @Version 1.0
 */
public class Combination3 {
    static Map<Character, String> map = new HashMap<>();
    static List<LinkedList<Character>> result = new ArrayList<>();
    static LinkedList<Character> path = new LinkedList<Character>();
    public static void main(String[] args) {
        Combination3 c = new Combination3();
        backTrack(0,"27");
        System.out.println(result);
    }

    public Combination3() {
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
    }

    /**
     * 回溯
     * @param index 指的是集合索引
     * @param str 待处理的数字字符串
     */
    public static void backTrack(int index, String str){
        if (index == str.length()){
            result.add(new LinkedList<>(path));
            return;
        }

        //确定当层遍历逻辑
        String letters = map.get(str.charAt(index));
        for (int i = 0; i < letters.length(); i++) {
            //处理当前节点
            path.addLast(letters.charAt(i));
            //递归
            backTrack(index+1,str);
            //回溯，取消相关操作
            path.removeLast();
        }
    }
}
